import java.util.HashSet;
import java.util.Set;

/**
 * @author LKQ
 * @date 2021/12/17 21:27
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        ListNode headA = new ListNode(1);
        ListNode l2 = new ListNode(9);
        ListNode l3 = new ListNode(1);
        ListNode l4 = new ListNode(2);
        ListNode l5 = new ListNode(4);
        ListNode l6 = new ListNode(3);
        headA.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;
        ListNode headB = new ListNode(3);
        headB.next = l4;
        Solution solution = new Solution();
        solution.getIntersectionNode(headA, headB);
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> visited = new HashSet<ListNode>();
        ListNode temp = headA;
        while (temp != null) {
            visited.add(temp);
            temp = temp.next;
        }
        temp = headB;
        while (temp != null) {
            if (visited.contains(temp)) {
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }
}
